//
// Created by Semir on 2020/5/17.
//

#include <iostream>

using namespace std;

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    explicit TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

void ConnectTreeNode(TreeNode* pRoot, TreeNode* pLeft, TreeNode* pRight) {
    if (pRoot == nullptr) {
        return;
    }
    pRoot->left = pLeft;
    pRoot->right = pRight;
}

TreeNode* BuildTree1() {
    auto* node1 = new TreeNode(10);
    auto* node2 = new TreeNode(6);
    auto* node3 = new TreeNode(14);
    auto* node4 = new TreeNode(4);
    auto* node5 = new TreeNode(8);
    auto* node6 = new TreeNode(12);
    auto* node7 = new TreeNode(16);
    ConnectTreeNode(node1, node2, node3);
    ConnectTreeNode(node2, node4, node5);
    ConnectTreeNode(node3, node6, node7);

    return node1;
}

TreeNode* Convert(TreeNode* pRootOfTree, TreeNode* parent, TreeNode*& first) {
    if (pRootOfTree == nullptr) {
        return nullptr;
    }
    TreeNode* pNode = nullptr;
    if (pRootOfTree->left) {
        pNode = Convert(pRootOfTree->left, parent, first);
    } else if (parent) {
        pNode = parent;
    }

    if (pNode) {
        pNode->right = pRootOfTree;
    } else {
        first = pRootOfTree;
    }
    pRootOfTree->left = pNode;

    TreeNode* nNode = pRootOfTree;
    if (pRootOfTree->right) {
        nNode = Convert(pRootOfTree->right, pRootOfTree, first);
    }
    return nNode;
}

TreeNode* Convert(TreeNode* pRootOfTree) {
    if (pRootOfTree == nullptr) {
        return nullptr;
    }
    TreeNode* first = nullptr;
    Convert(pRootOfTree, nullptr, first);
    return first;
}

int main() {
    TreeNode* root = BuildTree1();
    TreeNode* node = Convert(root);
    cout << node << endl;
    return 0;
}